package 笔试.电信2016.数组;

//给定一个已经排好序的字符串数组,空字符串散布在该数组中,编写一个函数寻找一个 给定字符串的位置。
public class Main {
    public static void main(String[] args) {
        String[] s = {"at", "", "", "", "ball", "", "", "car", "", "", "dad", "", ""};
        System.out.println(search(s, 0, s.length - 1, "ball"));
        System.out.println(search(s, 0, s.length - 1, "car"));
    }

    //二分查找，由于已经告诉字符串数组是有序的，可以使用二分法
    public static int search(String[] s, int low, int high, String x) {
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            while (s[mid].equals("") && mid <= high) {//碰到空字符串就右移
                mid++;
            }
            if (s[mid].equals(x)) {
                return mid;
            } else if (s[mid].compareTo(x) < 0) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
